class Pairs {
  public key: number;
  public value: string;
  constructor(key: number, value: string) {
    this.key = key;
    this.value = value;
  }
}
/**链式地址哈希表 */
class HashMapChaining {
  #size: number; //键值对数量
  #capacity: number; //哈希表数量
  #loadFactor: number; //负载因子
  #extendRatio: number; //扩容倍数
  #buckets: Pairs[][]; //桶数组

  constructor() {
    this.#size = 0; // 键值对数量
    this.#capacity = 4;// 哈希表容量
    this.#loadFactor = 2.0 / 3.0;// 触发扩容的负载因子阈值
    this.#extendRatio = 2;
    this.#buckets = new Array(this.#capacity).fill(null).map(() => []); // 桶数组
  }
  /**哈希函数 */
  #hashFunc(key: number): number {
    return key % this.#capacity;
  }
  /** 负载因子 */
  #getLoadFactor(): number {
    return this.#size / this.#capacity;
  }
  /**
   * 查询操作
   * @param key 
   */
  get(key: number): string | null {
    let index = this.#hashFunc(key);
    let bucket = this.#buckets[index];
    // 遍历桶中的链表，找到对应的key，返回value
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        return bucket[i].value;
      }
    }
    return null; // 没有找到对应的key，返回null
  }
  /**
   * 插入操作
   * @param key 键
   * @param value 值
   */
  put(key: number, value: string): void {
    // 当负载因子超过阈值，进行扩容
    if (this.#getLoadFactor() > this.#loadFactor) {
      this.#extend();
    }
    const index = this.#hashFunc(key);
    let bucket = this.#buckets[index];
    // 遍历桶中的链表，找到对应的key，更新value
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        bucket[i].value = value;
        return;
      }
    }
    // 没有找到对应的key，插入新的键值对
    bucket.push(new Pairs(key, value));
    this.#size++;
  }
  /**
   * 删除操作
   * @param key
   */
  remove(key: number): void {
    let index = this.#hashFunc(key);
    let bucket = this.#buckets[index];
    // 遍历桶中的链表，找到对应的key，删除
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i].key === key) {
        bucket.splice(i, 1);
        this.#size--;
        return;
      }
    }
  }
  // 扩容
  #extend(): void {
    // 暂存旧桶数组
    let oldBuckets = this.#buckets;
    // 初始化扩容后的桶数组
    this.#capacity *= this.#extendRatio;
    this.#buckets = new Array(this.#capacity).fill(null).map(() => []);
    this.#size = 0;
    // 遍历旧桶数组，将键值对重新插入新桶数组
    for (let bucket of oldBuckets) {
      for (let pair of bucket) {
        this.put(pair.key, pair.value);
      }
    }
  }
  /** 打印 */
  print(): void {
    for (let bucket of this.#buckets) {
      let res: Array<string | undefined> = [];
      for (let pair of bucket) {
        res.push(pair.key + ' -> ' + pair.value);
      }
      console.log(res);
    }
  }
}
// 测试类
const hashMap = new HashMapChaining();
hashMap.put(1, 'a');
hashMap.put(2, 'b');
hashMap.put(3, 'c');
hashMap.put(4, 'd');
hashMap.print();